package com.ry.day1129;

public class LC109 {

    static class Solution {
        /**
         * @param triangle: a list of lists of integers
         * @return: An integer, minimum path sum
         */
        public int minimumTotal(int[][] triangle) {
            //动态规划
            int[][] arr = triangle;
            if(arr ==null || arr.length ==0) return 0;
            if(arr.length ==1) return arr[0][0];
            int n= arr.length;
            for (int row = n-2; row >=0 ; row--) {
                for (int col = 0; col <arr[row].length ; col++) {
                    arr[row][col] += Math.min(arr[row+1][col],arr[row+1][col+1]);
                }
            }

            return arr[0][0];
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        int[][] arr1 = {
                {2},
                {3,4},
                {6,5,7},
                {4,1,8,3},
        };

        System.out.println(obj.minimumTotal(arr1));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
109 · 数字三角形
算法
中等
通过率
34%

题目
题解95
笔记
讨论99+
排名
记录
描述
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


如果只用额外空间复杂度
O
(
n
)
O(n)完成，可以获得加分，其中n是数字三角形的总行数。

样例
样例 1：

输入：

triangle = [
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
输出：

11
解释：

从顶到底部的最小路径和为11 （ 2 + 3 + 5 + 1 = 11）。

样例 2：

输入：

triangle = [
     [2],
    [3,2],
   [6,5,7],
  [4,4,8,1]
]
输出：

12
解释：

从顶到底部的最小路径和为12 （ 2 + 2 + 7 + 1 = 12）。

标签
相关题目

110
最小路径和
简单
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
42/1586
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
